/*
leetcode 49. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

 

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:

输入: strs = [""]
输出: [[""]]
示例 3:

输入: strs = ["a"]
输出: [["a"]]
 

提示：

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
*/

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    
    unordered_map<string, vector<string>> hashTable; // 定义哈希表

    //遍历输入的字符串数组
    for (const string& str : strs) {

        string key = str; //将当前字符串赋值给 key
        
        sort(key.begin(), key.end()); // 将字符串排序，作为哈希表的键
        
        // 将原始字符串 str 插入到哈希表中，键为排序后的 key
        //在 vector<string> 类型的值末尾添加一个新的元素（str），vector 是个动态数组
        hashTable[key].push_back(str); 
    }

    vector<vector<string>> result; // 存储最终结果

    for (auto& entry : hashTable) {

        result.push_back(entry.second); // 遍历哈希表，将每个键对应的值（即一个字母异位词的分组）插入到结果数组中
    }

    return result;
}

int main() {
    vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> result = groupAnagrams(strs);

    for (const auto& group : result) {
        for (const auto& word : group) {
            cout << word << " ";
        }
        cout << endl;
    }

    return 0;
}

/*
输入数据：
假设输入是以下字符串数组：
vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};

1. 初始化：
首先，定义一个空的哈希表：
unordered_map<string, vector<string>> hashTable;

2. 遍历输入字符串并构建哈希表：
我们开始遍历 strs 数组，每次拿到一个字符串，然后对其进行处理。

第一轮： 处理字符串 "eat"
key 赋值为 "eat"。
对 key 排序，得到 "aet"。
在哈希表中查找 "aet"，发现没有，所以自动创建新的键值对：hashTable["aet"] = ["eat"]。
哈希表此时是：
hashTable = {
    "aet": ["eat"]
};

第二轮： 处理字符串 "tea"
key 赋值为 "tea"。
对 key 排序，得到 "aet"。
查找哈希表，发现 "aet" 已经存在，直接将 "tea" 加入对应的 vector：hashTable["aet"].push_back("tea")。
哈希表此时是：
hashTable = {
    "aet": ["eat", "tea"]
};

第三轮： 处理字符串 "tan"
key 赋值为 "tan"。
对 key 排序，得到 "ant"。
查找哈希表，发现 "ant" 不存在，自动创建新的键值对：hashTable["ant"] = ["tan"]。
哈希表此时是：
hashTable = {
    "aet": ["eat", "tea"],
    "ant": ["tan"]
};

第四轮： 处理字符串 "ate"
key 赋值为 "ate"。
对 key 排序，得到 "aet"。
查找哈希表，发现 "aet" 已经存在，直接将 "ate" 加入对应的 vector：hashTable["aet"].push_back("ate")。
哈希表此时是：
hashTable = {
    "aet": ["eat", "tea", "ate"],
    "ant": ["tan"]
};

第五轮： 处理字符串 "nat"
key 赋值为 "nat"。
对 key 排序，得到 "ant"。
查找哈希表，发现 "ant" 已经存在，直接将 "nat" 加入对应的 vector：hashTable["ant"].push_back("nat")。
哈希表此时是：
hashTable = {
    "aet": ["eat", "tea", "ate"],
    "ant": ["tan", "nat"]
};

第六轮： 处理字符串 "bat"
key 赋值为 "bat"。
对 key 排序，得到 "abt"。
查找哈希表，发现 "abt" 不存在，自动创建新的键值对：hashTable["abt"] = ["bat"]。
哈希表此时是：
hashTable = {
    "aet": ["eat", "tea", "ate"],
    "ant": ["tan", "nat"],
    "abt": ["bat"]
};

3. 构建结果：
接下来，我们遍历哈希表，将每组异位词添加到结果 result 中。

vector<vector<string>> result;
for (auto& entry : hashTable) {
    result.push_back(entry.second); // 将每组异位词加入结果
}

遍历哈希表：
第一组：entry.first = "aet", entry.second = ["eat", "tea", "ate"]。
将 ["eat", "tea", "ate"] 添加到 result 中。

第二组：entry.first = "ant", entry.second = ["tan", "nat"]。
将 ["tan", "nat"] 添加到 result 中。

第三组：entry.first = "abt", entry.second = ["bat"]。
将 ["bat"] 添加到 result 中。

最终 result 是：
result = {
    {"eat", "tea", "ate"},
    {"tan", "nat"},
    {"bat"}
};

4. 返回结果：
函数返回 result，即字母异位词的分组。
*/
